#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<map>
#include<vector>
#include <string>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

//打印map的键值对
template<class K, class V>
void print(const map<K, V>& map) {
    for (const auto& pair : map) {
        cout << pair.first << " : " << pair.second << endl;
    }
    cout << endl;
}

// 哈夫曼树节点
typedef class Huffman_Node {
public:
    char ch;
    unsigned int _weight;
    Huffman_Node* left, * right;

    Huffman_Node(char x, unsigned int weight) 
    :ch(x),
    _weight(weight),
    left(nullptr),
    right(nullptr)
    {}
}Node;


// 比较函数，用于优先队列
class Compare {
public:
    bool operator()(Node* l, Node* r) {
        return (l->_weight > r->_weight);
    }
};

// 构建哈夫曼树
Node* Build_Huffman_Tree(const map<char, unsigned int>& weights) {
    priority_queue<Node*, vector<Node*>, Compare> minHeap;

    // 创建叶子节点，并构建最小堆
    for (auto p : weights) {
        minHeap.push(new Node(p.first, p.second));
    }

    // 构建哈夫曼树
    while (minHeap.size() != 1) {
        Node* left = minHeap.top();
        minHeap.pop();

        Node* right = minHeap.top();
        minHeap.pop();

        Node* top = new Node(' ', left->_weight + right->_weight);
        top->left = left;
        top->right = right;
        minHeap.push(top);
    }

    return minHeap.top();
}


// 递归函数来生成哈夫曼编码
void Huffman_Codes(Node* root, string str, map<char, string>& huffmanCode) {
    if (root == nullptr) {
        return;
    }
    if (root->ch != ' ') {
        huffmanCode[root->ch] = str;
    }
    //采用递归，跟树的遍历类似
    Huffman_Codes(root->left, str + "0", huffmanCode);
    Huffman_Codes(root->right, str + "1", huffmanCode);
}

//求平均编码长度
double Huffman_mean(const map<char, string>& huffmanCode, const map<char, unsigned int>& weights) {
    double mean = 0;
    double totalWeight = 0;
    // 计算所有字符权重的总和
    for (const auto& weight : weights) {
        totalWeight += weight.second;
    }
    // 计算平均编码长度
    for (const auto& code : huffmanCode) {
        mean += code.second.length() * weights.at(code.first);
    }
    mean = mean / totalWeight;
    return mean;
}

//进行哈夫曼编码的解码
string Port_Code(const string& rany, Node* root) {
    if (rany.empty() || root == nullptr) {
        return "";
    }
    string answer = "";
    Node* current = root;
    for (int count = 0; count < rany.length(); ++count) {
        // 根据当前位是'0'还是'1'，移动到左子树或右子树
        if (rany[count] == '0') {
            current = current->left;
        }
        else if (rany[count] == '1') {
            current = current->right;
        }

        // 检查是否到达叶子节点
        if (current->left == nullptr && current->right == nullptr) {
            answer += current->ch; // 将当前节点的字符添加到答案中
            current = root; // 重置为根节点，准备解码下一个字符
        }
    }
    return answer; // 返回解码后的字符串
}

int main()
{
    int n;
    cin >> n; // 读取字符个数
    map<char, unsigned int> Weight_Map;
    map<char, string>Code_Map;
    // vector<pair<char, unsigned int>> vec; // 用于排序的临时vector
    //读取字符对应的权重
    for (int i = 0; i < n; i++)
    {
        char x;//字符
        unsigned int y;//字符对应的权重
        cin >> x >> y;      
        Weight_Map[x] = y;
    }
    //读取要解码的数据
    string rany;// 要解码的数据
    cin.ignore(); // 忽略之前读取的换行符
    getline(cin, rany, '#');
    //进行哈夫曼编码
    Node* root = Build_Huffman_Tree(Weight_Map);
    Huffman_Codes(root, "", Code_Map);
    //自动推导
    cout << "对应的哈夫曼编码如下：" << endl;
    print(Code_Map);

    double answer=Huffman_mean(Code_Map, Weight_Map);
    cout << "对应的平均编码长度为" << answer << endl;
    
    string code = Port_Code(rany, root);
    cout << "对应的译码为" << code << endl;
}
